//----------------------------------------------------------------------------
//  ,-.
// /_\___ ,   Ninja Framework
// '  ___\    (C) Riccardo Capra - http://riccar.do
//  //   \\
//----------------------------------------------------------------------------
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.
//----------------------------------------------------------------------------

#ifndef NJ_ATOMIC_STACK_H
#	define NJ_ATOMIC_STACK_H

#	include "NjNinjaSyncLib.h"
#	include "NjAtomic.h"
#	include "NjAssert_config.h"
#	include "NjConfiguration.h"

	/// \brief Implements a stack (a lifo) where push and pop operations are atomic
	class NjAtomicStack
	{
	public:
		class FlushNode;

		/// \brief The node type to be pushed or pop
		/// 
		/// You can inherit from this class and implement your own node type
		class Node
		{
			friend class NjAtomicStack;
			friend class NjAtomicStack::FlushNode;

		public:
			NJ_TRIVIAL_DEFAULT_CONSTRUCTOR(Node);
			NJ_TRIVIAL_DESTRUCTOR(Node);
			
		private:
			/// \brief The next node in the stack
			Node * m_pNext;

			NJ_DISABLE_COPY(Node);
		};

		/// \brief Node type returned when all the stack is flushed
		///
		/// You can use this node type to iterate on the stack entries
		class FlushNode
		{
			friend class NjAtomicStack;

		public:
			/// \brief Returns the next node in the stack
			FlushNode * GetNext();

			/// \brief Returns the undelying node that was originally pushed
			///
			/// You can then static_cast it to your node type
			Node * GetNode();

		private:
			NJ_DISABLE_INSTANCE(FlushNode);
		};

		/// \brief Default constructor for NjAtomicStack
		///
		/// The stack is created empty
		NjAtomicStack();
		NJ_TRIVIAL_DESTRUCTOR(NjAtomicStack);

		/// \brief Pushes a \em pNode into the stack
		/// \param pNode the node to be pushed
		/// \pre \em pNode must be not NJ_NULL
		void Push(Node * pNode);

		/// \brief Pushes all the nodes starting from \em pNode up to the end into the stack
		///
		/// Nodes order is preserved
		/// \param pNode the first node to be pushed
		/// \pre \em pNode must be not NJ_NULL
		void PushRange(FlushNode * pNode);

		/// \brief Pushes all the nodes starting from \em pNode up to \em pBeforeEnd included into the stack
		///
		/// Nodes order is preserved
		/// \param pNode the first node to be pushed
		/// \param pBeforeEnd the last node (included) to be pushed
		/// \pre \em pNode and \em pBeforeEnd must be not NJ_NULL
		void PushRange(FlushNode * pNode, FlushNode * pBeforeEnd);

		/// \brief pops the last node that was pushed into the stack
		///
		/// You can then static_cast it to your node type
		/// \return The last node that was into the stack or NJ_NULL if the stack is empty
		Node * Pop();

		/// \brief Empties all the stack and returns a singly linked list of the nodes that previously where in it
		///
		/// Nodes order is preserved
		FlushNode * Flush();

	private:
		/// \brief Private internal implementation
		class Static;
		
		/// \brief The underlying type used to store the stack head
		typedef NjUint64 Pointer;

		/// \var static const Pointer ADDRESS_MASK
		/// \brief The bit mask where pointers will be stored
		///
		/// On 64 bit architectures is assumed that not all the 64 bits
		/// are used by the operating system to store pointers
#	if NJ_PLATFORM_OS_WIN
		static const Pointer ADDRESS_MASK  = 0x0000FFFFFFFFFFFFULL;
#	elif NJ_PLATFORM_OS_LINUX
		static const Pointer ADDRESS_MASK  = 0x00000000FFFFFFFFULL;
#	else // NJ_PLATFORM_OS_WIN || NJ_PLATFORM_OS_LINUX
#		error "Unsupported build configuration"
#	endif // NJ_PLATFORM_OS_WIN || NJ_PLATFORM_OS_LINUX

		/// \brief A tag mask used to avoid the ABA problem
		/// \sa http://en.wikipedia.org/wiki/ABA_problem
		static const Pointer TAG_MASK = ~ADDRESS_MASK;

		/// \brief The first bit of the tag mask
		static const Pointer TAG_INCREMENT = ADDRESS_MASK+1;

		/// \brief The underlying type used atomically operate on the stack head
		typedef NjAtomic<Pointer> AtomicPointer;

#	if NJ_ASSERT_ENABLED
		/// \brief Ensures (through assertion) that pointers will fit in the \em ADDRESS_MASK
		static void AssertValidAddressMask();
#	endif // NJ_ASSERT_ENABLED

		/// \brief The head of the stack
		AtomicPointer m_kHeader;

		NJ_DISABLE_COPY(NjAtomicStack);
	};

#	include "NjAtomicStack_inline.h"

#endif // NJ_ATOMIC_STACK_H
